package com.imooc.study.imoocstudy.datastructure.sortalgorithm;

import java.util.Arrays;
import java.util.Map;

/**
 * 希尔排序算法
 * 时间复杂度：O(n^1.5)
 */
public class ShellSortTest {

    public static void shellSort(int array[]){

        int temp = 0;
        int incre = array.length;

        while(true){
            incre = incre/2;

            for(int k = 0;k<incre;k++){    //根据增量分为若干子序列

                for(int i=k+incre;i<array.length;i+=incre){

                    for(int j=i;j>k;j-=incre){
                        if(array[j]<array[j-incre]){
                            temp = array[j-incre];
                            array[j-incre] = array[j];
                            array[j] = temp;
                        }else{
                            break;
                        }
                    }
                }
            }

            if(incre == 1){
                break;
            }
        }
    }

    public static void main(String[] args) {
        int a[] = new int[]{19,80,2,7,4,1,10,12,88,44,33,29,80};

        ShellSortTest.shellSort(a);

        Arrays.stream(a).forEach(System.out::println);
    }
}
